# coding=utf-8
'''
伪代码如下
********************************************************************

创建k个点作为初始的质心点（随机选择）
当任意一个点的簇分配结果发生改变时
       对数据集中的每一个数据点
              对每一个质心
                     计算质心与数据点的距离
              将数据点分配到距离最近的簇
       对每一个簇，计算簇中所有点的均值，并将均值作为质心

********************************************************************
'''
from numpy import *
from matplotlib import pyplot as plt


def loadDataSet(fileName):
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split(',')
        fltLine = map(float, curLine[:-1])
        dataMat.append(fltLine)
        # print dataMat
    return dataMat

# 计算两个向量的距离，用的是欧几里得距离


def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2)))

# 随机生成初始的质心（ng的课说的初始方式是随机选K个点）


def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k, n)))
    for j in range(n):
        minJ = min(dataSet[:, j])
        rangeJ = float(max(array(dataSet)[:, j]) - minJ)
        centroids[:, j] = minJ + rangeJ * random.rand(k, 1)
    return centroids


def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m, 2)))  # create mat to assign data points
    # to a centroid, also holds SE of each point
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):  # for each data point assign it to the closest centroid
            minDist = inf
            minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j, :], dataSet[i, :])
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist**2
        # print centroids
        for cent in range(k):  # recalculate centroids
            ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[
                0]]  # get all the point in this cluster
            # assign centroid to mean
            centroids[cent, :] = mean(ptsInClust, axis=0)
    # print clusterAssment[:,0]
    return centroids, clusterAssment


def show(dataSet, k, centroids, clusterAssment):
    numSamples, dim = dataSet.shape
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    for i in xrange(numSamples):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])
    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=6)
    plt.show()


def evaluateResult():
    pass


def main():
    dataMat = mat(loadDataSet('iris.data.txt'))
    myCentroids, clustAssing = kMeans(dataMat, 3)
    # print myCentroids
    show(dataMat, 3, myCentroids, clustAssing)


if __name__ == '__main__':
    main()
